#include <stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node *next;
} *first=NULL, *third = NULL;

void create(int arr[], int n) {
    struct Node *t, *last;
    first = (struct Node *)malloc(sizeof(struct Node));
    first->data = arr[0];
    first->next = NULL;
    last = first;

    for(int i = 1; i < n; i++) {
        t = (struct Node *)malloc(sizeof(struct Node));
        t->data = arr[i];
        t->next = NULL;
        last->next=t;
        last=t;
    }
}

void displayLL(struct Node *p) {
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void rDisplay(struct Node *p) {
    if (p != NULL) {
        printf("%d ", p->data);
        rDisplay(p->next);
    }
}

int count(struct Node *p) {
    int count = 0;

    while(p != NULL) {
        count++;
        p = p->next;
    }

    return count;

}

int rCount(struct Node *p) {
    if(p == NULL) 
    {
        return 0;
    }
        return 1 + rCount(p->next);
}

void sum(struct Node *p) {
    int s = 0;
    while (p != NULL) {
        s += p->data;
        p = p->next;
    }
    printf("Sum: %d ", s);
}

int max(struct Node *p) {
    // int m = p->data;
    int m = -32768;
    while (p != NULL) {
        if (m < p->data) {
            m = p->data;
        }
        p = p->next;
    }
    return m;
}

int rMax(struct Node *p) {
    int x = 0;
    if (p == NULL) {
        return -32768; 
    }
    x = rMax(p->next);
    return x > p->data ? x : p->data;
}

struct Node * search(struct Node *p, int target) {
    while (p != NULL)
    {
        if (p->data == target) {
            return p;
        }
        p = p->next;
    }
    return NULL;    
}

struct Node * rSearch(struct Node *p, int target) {
    if (p == NULL) {
        return NULL;
    } 
    if (p->data == target)
        return p;
    rSearch(p->next, target);
}

// void insertFirst(struct Node *p, int num) {
//     struct Node *t;
//     t = (struct Node *)malloc(sizeof(struct Node));
//     t->data = num;
//     t->next = first;
//     first = t;
// }

void insert(struct Node *p, int data, int pos) {

    struct Node * t = (struct Node *)malloc(sizeof(struct Node));
    t->data = data;
    
    for (int i = 0; i < pos - 1 & p !=NULL; i++)
    {
        p = p->next;
    }
    if (p == NULL || pos < 0) 
        return;
    if (pos == 0) 
    {
        t->next = first;
        first = t;
    }
    else 
    {
        t->next = p->next;
        p->next = t;
    }
}

void insertLast(int num) {
    struct Node *t, *last;

    t = (struct Node *)malloc(sizeof(struct Node));
    t->data = num;
    t->next = NULL;

    if (first == NULL)
    {
        first = last = t;
    }
    else 
    {
        last->next = t;
        last = t;
    }
}

void addElementSortedLL(struct Node *p, int num) {
    struct Node *t, *q = NULL;
    t = (struct Node *)malloc(sizeof(struct Node));
    t->data = num;
    t->next = NULL;
    if (p == NULL) 
    {
        first = t;
    }
    else if (num < p->data) 
    {
        t->next = first;
        first = t;
    }
    else 
    {
        while (p && num > p->data)
        {
            q = p;
            p = p->next;
        }
        t->next = q->next;
        q->next = t;
    }
}

void del(struct Node *p, int pos) 
{
    struct Node *q;
    int x;
    if (pos < 1) 
    {
        return;
    }
    else if (pos == 1) 
    {
        q = first;
        x = first->data;
        first = first->next;
        free(q);
    }
    else 
    {
        for (int i = 0; p && i < pos - 1; i++)
        {
            q = p;
            p = p->next;
        }
        if (p) 
        {
            q->next = p->next;
            x = p->data;
            free(p);
        }
    }
}

int sortCheck(struct Node *p)
{
    int q = -32768;
    while (p != NULL)
    {
        if(p->data < q) 
        {
            return 0;
        }
        q = p->data;
        p = p->next;
    }
    return 1;
}

void removeDuplicate(struct Node *p) 
{
    struct Node *q = p->next;
    while (q != NULL)
    {
        if (p->data == q->data) 
        {
            p->next = q->next;
            free(q);
            q = p->next;
        }
        else
        {
            q=q->next;
            p=p->next;
        }
    }
}

void rev1(struct Node *p)
{
   int *arr, i = 0, c = count(p);
   arr = (int *)malloc(sizeof(int) * c);

   while (p != NULL)
   {
       arr[i] = p->data;
       i++;
       p = p->next;
   }
    p = first;
    i--;
    while (p != NULL)
   {
       p->data = arr[i];
       i--;
       p = p->next;
   }
}

void reverse (struct Node *p)
{
    struct Node *q, *r;
    q = r = NULL;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    first = q;
}

void rev3(struct Node *q, struct Node *p)
{
    if(p)
    {
        rev3(p, p->next);
        p->next = q;
    }
    else
    {
        first = q;
    }
}

void concat(struct Node *p, struct Node *q)
{
    while (p->next)
    {
        p=p->next;
    }
    p->next = q;
}

void merge(struct Node * p, struct Node* q)
{
    struct Node *last;
    if (p->data < q->data)
    {
        third = last = p;
        p = p->next;
        last->next = NULL;
    }
    else 
    {
        third = last = q;
        q = q->next;
        last->next = NULL;
    }
    while (p !=NULL && q !=NULL)
    {
        if (p->data < q->data)
        {
            last->next = p;
            last = p;
            p = p->next;
            last->next = NULL;
        }
        else
        {
            last->next = q;
            last = q;
            q = q->next;
            last->next = NULL;
        }
    }
    if(p != NULL) 
    {
        last->next = p;
    }
    else
    {
        last->next = q;
    }
}

int main() {
    int arr[] = {3, 7, 11, 19, 8};
    struct Node *second = NULL;
    create(arr, 5);
    displayLL(first);
    // rDisplay(first);
    count(first);
    // printf("\nrCount: %d", rCount(first));
    // sum(first);
    // printf("Max: %d ", max(first));
    // printf("Found?: %d ", rSearch(first, 7));
    insert(first, 10, 3);
    del(first, 2);
    displayLL(first);
    return 0;
}

